#pragma once
#include<time.h>
#include<iostream>
#include"Graph_Functions.h"
#include<algorithm>

vector<pair<int, int> > full_graph(int k)
{
	vector<pair<int, int> > graph;

	for(int i = 0; i<k; ++i)
		for(int j = i + 1; j<k; ++j)
		{
			int possibility = rand()%2;
			if (possibility) graph.push_back(make_pair(i, j));
			else
				graph.push_back(make_pair(j, i));
		}
		return graph;
}

void Full_Graph(int m)
{
	time_t t;
	t = clock();
	vector<pair<int, int> > graph = full_graph(m);
	auto experimental_graph = compact_graph(m, graph); 
}

vector<pair<int, int> > random_graph(int k, double poss)
{
	vector<pair<int, int> > graph;

	for(int i = 0; i<k; ++i)
		for(int j = i + 1; j<k; ++j)
		{
			double randd = (rand()%100)/100.0;
			if (randd > poss)continue;
			int possibility = rand()%2;
			if (possibility) graph.push_back(make_pair(i, j));
			else
				graph.push_back(make_pair(j, i));
		}
		return graph;
}

void Random_Graph(int m, double poss)
{
	time_t t;
	t = clock();
	vector<pair<int, int> > graph = random_graph(m, poss);
	auto experimental_graph = compact_graph(m, graph); 
}

vector<pair<int, int> > random_acyclic_graph(int m, double poss){

	vector<pair<int, int> > graph;

	vector<int> sorted;
	for(int i = 0; i<m; ++i)sorted.push_back(i);
	random_shuffle(sorted.begin(), sorted.end());

	for(int i = 0; i<m; ++i)
		for(int j = i + 1; j<m; ++j)
		{
			double a = (rand()%100)/100.0;
			if (a > poss)continue;
			if (sorted[i] > sorted[j]) graph.push_back(make_pair(i, j));
			else
				graph.push_back(make_pair(j, i));
		}

		return graph;
}

void Random_Acyclic_Graph(int m, double poss)
{
	vector<pair<int, int> > graph = random_acyclic_graph(m, poss);
	auto experimental_graph = compact_graph(m, graph); 
}

void cool_test_for_different_types_of_graphs()
{
	for(int size = 1; size <= 13; ++size)Full_Graph(size);

	for(int size = 1; size <= 30; ++size, cerr << "size "<< size << " is going now\n")
		for(int possibility = 0; possibility <= 80; ++possibility)
		{
			double poss = possibility/100.0;
			Random_Graph(size, poss);
			Random_Acyclic_Graph(size, poss);
		}

	cerr << "making graph is ok!\n"; 
}

void test_topological_sort()
{
	for(int m = 2; m < 30; ++m, cerr << "size in top_sirt now: " << m << "\n")
		for(int possibility = 0; possibility < 80; ++possibility)
		{
			double poss = possibility/100.0;

			vector<pair<int, int> > graph = random_acyclic_graph(m, poss);
			auto experimental_graph = compact_graph(m, graph); 
			
			vector<int> topological_sort = top_sort(experimental_graph);

			for(int i = 0; i<m; ++i)
			{
				vector<int>list_of_vertices = experimental_graph->get_list_adjacents(i);
				for(int j = 0; j < list_of_vertices.size(); ++j)
				{
					int to = list_of_vertices[j]; 
					if (topological_sort[i] < topological_sort[to]) cerr << "FALSE!!!\n";
					
				}
			}
		}
}

class DFS_Testing
{
	
public:
	vector<int>visited;
	vector<vector<int> >edge;
	vector<vector<int> >visited_edge;
	int FIRST_TYPE_OPERATION;
	int FIRST_TYPE_EDGE_OPERATION;

	void initialize(const unique_ptr<IGraph> & graph, int start)
	{
		int size = graph->get_number_of_vertice();
		FIRST_TYPE_OPERATION = 1;
		FIRST_TYPE_EDGE_OPERATION = 2;
		visited.assign(size, 0);
		visited_edge.assign(size, vector<int>(size, 0));
		edge.assign(size, vector<int>(size, 0));
		for(int vertex = 0; vertex < size; ++vertex)
		{
			vector<int>vertices = graph->get_list_adjacents(vertex);
			for(int i = 0; i<vertices.size(); ++i)
			{
				int to = vertices[i];
				edge[vertex][to] = 1;
				edge[to][vertex] = 1;
			}
		}
	}

	void enter_vertex (const unique_ptr<IGraph> & graph, int vertex, vector<int> & color)
	{
		++visited[vertex];
	}
		
	void before_edge (const unique_ptr<IGraph> & graph, int vertex, int to, vector<int> & color)
	{
		++visited_edge[vertex][to];
		++visited_edge[to][vertex];
	}
		
	void after_edge (const unique_ptr<IGraph> & graph, int vertex, int to, vector<int> & color)
	{
		
	}
	
	void exit_vertex (const unique_ptr<IGraph> & graph, int vertex, vector<int> & color)
	{
		
	}

	void final(const unique_ptr<IGraph> & graph)
	{
		for(int i = 0; i<visited.size(); ++i)
			if (visited[i] != 1){cerr << "DFS trouble!\n";}
		for(int i = 0; i<visited_edge.size(); ++i)
			for(int j = 0; j<visited_edge[i].size(); ++j)
				if (visited_edge[i][j] != edge[i][j])cerr << "Edges trouble!\n";
	}

};


void DFS_Test()
{
	for(int size = 3; size < 20; ++size, cerr << "size: " << size << "\n")
		for(double possibility = 1; possibility <= 50; ++possibility)
		{
			vector<pair<int, int> > graph = random_graph(size, possibility/100.0);
			auto experimental_graph = compact_graph(size, graph);
			DFS_Testing testdfs;
			commondfs<DFS_Testing> dfs (experimental_graph, -1, testdfs);
			dfs.dfscycle(experimental_graph, testdfs);
		}


}

void BFS_Test()
{
	for(int size = 3; size < 20; ++size, cerr << "size: " << size << "\n")
		for(double possibility = 1; possibility <= 50; ++possibility)
		{
			vector<pair<int, int> > graph = random_graph(size, possibility/100.0);
			auto experimental_graph = compact_graph(size, graph);
			int vertex = rand()%size;
			vector<int> min_distance = BFS(experimental_graph, vertex);
			vector<vector<int> >min_real_distance;
			min_real_distance.assign(size, vector<int>(size, 1000000));
			for(int from = 0; from < size; ++from)
			{
				vector<int> adj = experimental_graph->get_list_adjacents(from);
				for(int i = 0; i < adj.size(); ++i)
				{
					int to = adj[i];
					min_real_distance[from][to] = 1;
					min_real_distance[to][from] = 1;
				}
			}
			for(int k = 0; k<size; ++k)
				for(int i = 0; i<size; ++i)
					for(int j = 0; j<size; ++j)
						min_real_distance[i][j] = min(min_real_distance[i][j], min_real_distance[i][k] + min_real_distance[k][j]);
			for(int i = 0; i<size; ++i)
				if (min_distance[vertex] < 1000000 && min_distance[vertex] != min_real_distance[vertex][i])cout << "BFS_FAIL!\n";
		}


}